package BinaryTree.Medium;

import DataStructures.BinaryTree;
import DataStructures.TreeNode;

public class LC0230 {
    class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 方法1：将二叉搜索树组织为链表，然后遍历链表查找目标值。
     * 实际上可以存在ArrayList中，ArrayList的第i个元素就是二叉树中第i小的元素。这样在频繁查找时可以有更佳性能。
     */
    public int KthSmallest(TreeNode root, int k) {
        ListNode[] list = innerRecursive(root);
        ListNode ptr = list[0];
        for (int i = 1; i < k; i++) {
            ptr = ptr.next;
        }

        return ptr.val;
    }

    /**
     * 将以node为根结点的子树转为链表
     */
    private ListNode[] innerRecursive(TreeNode node) {
        if (node == null) return new ListNode[]{null, null};

        ListNode thisNode = new ListNode(node.val);

        ListNode[] leftList, rightList;
        ListNode head, tail;
        if (node.left != null) {
            leftList = innerRecursive(node.left);
            head = leftList[0];
            leftList[1].next = thisNode;
        } else {
            head = thisNode;
        }

        if (node.right != null) {
            rightList = innerRecursive(node.right);
            thisNode.next = rightList[0];
            tail = rightList[1];
        } else {
            tail = thisNode;
        }

        return new ListNode[]{head, tail};
    }

    /**
     * 方法2：利用中序遍历。相比组织为链表的方法，这种方法可以不用遍历完整棵树，也不需要额外的存储空间来存储链表。
     */
    public static int KthSmallestInorder(TreeNode root, int k) {
        return innerRecursive2(root, k);
    }

    private static int innerRecursive2(TreeNode node, int k) {
        int leftResult, rightResult;
        if (node.left != null) {
            leftResult = innerRecursive2(node.left, k);
            if (leftResult >= 0) return leftResult; // 在左侧找到目标值
            else k += leftResult; // 左侧未找到，更新k
        } else {
            leftResult = 0; // 左子树为空时，leftResult只用于返回结点数，并且一定为0
        }

        if (k == 1) return node.val;

        if (node.right != null) {
            rightResult = innerRecursive2(node.right, k - 1);
            if (rightResult >= 0) return rightResult;
            else return leftResult - 1 + rightResult;
        } else return leftResult - 1; // 根节点不是目标结点，且右子树为空，返回结点数（左子树结点数+1）
    }

    public static void main(String[] args) {
        TreeNode root = BinaryTree.constructBinaryTree(new Integer[]{5, 3, 6, 2, 4, null, null, 1});
        System.out.println(KthSmallestInorder(root, 3));
    }
}
